package com.freedy.algorithm.kmp;

/**
 * @author Freedy
 * @date 2021/4/12 17:20
 */
public class KMPAlgorithm {
    public static void main(String[] args) {
        String a = "BBC ABCDAB ABCDABCDABDE";
        String b = "ABCDABD";
        System.out.println(kmpMatch(a,b));
    }

    public static int kmpMatch(String str1, String str2) {
        int[] next = kmpNext(str2);
        for (int i = 0, j = 0; i < str1.length(); i++) {
            //当str1.charAt(i)!=str2.charAt(j)时
            while (j>0&&str1.charAt(i)!=str2.charAt(j)){
                j=next[j-1];
            }
            if (str1.charAt(i)==str2.charAt(j)){
                j++;
            }
            if (j==str2.length()){
                return i-j+1;//找到了
            }
        }
        return -1;
    }

    /**
     * 获取一个字符串的部分匹配值
     * @param dest 字串
     * @return 匹配表
     */
    public static int[] kmpNext(String dest) {
        int[] next = new int[dest.length()];
        next[0] = 0;//如果字符串的长度为一，部分匹配值为0
        for (int i = 1, j = 0; i < dest.length(); i++) {
            //条件满足时,部分匹配值就要+1
            while (j > 0 && dest.charAt(i) != dest.charAt(j)) {
                j = next[j - 1];
            }
            if (dest.charAt(i) == dest.charAt(j)) {
                j++;
            }
            next[i] = j;
        }
        return next;
    }

}
